package Leetcode.数组字符串;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: kirito
 * @Date: 2024/3/17 0:59
 * @Description:
 * 给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。
 *
 * 你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：
 *
 * 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
 * 返回你在矩阵中能够 移动 的 最大 次数。
 */

public class maxMoves {
    /**
     * 把所有行坐标加入到集合中，作为出发点。然后对其依次遍历，对每一个单元格，找到下一个列的相邻单元格，
     * 并判断是否严格大于当前单元格。
     * 如果是，说明可以移动到达。把所有可到达的单元格行坐标加到集合中，并用于下一轮的搜索。
     *
     * 当到达最后一列或者集合为空，搜索结束，返回矩阵中移动的最大次数。
     * @return
     */
    public int maxMoves(int[][] grid) {
        // 获取网格的行数和列数
        int m = grid.length, n = grid[0].length;
        // 使用HashSet存储每一列的最小值所在的行
        Set<Integer> q = new HashSet<>();
        for (int i = 0; i < m; i++) {
            q.add(i);
        }
        // 遍历每一列，从第二列开始
        for (int j = 1; j < n; j++) {
            // 创建一个新的HashSet q2，用于存储新的行号
            Set<Integer> q2 = new HashSet<>();
            // 遍历当前列的每一行的行号
            for (int i : q) {
                // 遍历上一列的三个相邻的行号
                for (int i2 = i - 1; i2 <= i + 1; i2++) {
                    // 如果当前行号i2有效，并且上一列的当前行号i的值小于i2的值
                    if (0 <= i2 && i2 < m && grid[i][j - 1] < grid[i2][j]) {
                        // 将i2添加到q2中
                        q2.add(i2);
                    }
                }
            }
            // 将q2赋值给q，用于下一列的遍历
            q = q2;
            // 如果q为空，说明没有有效的行号，即无法到达右边界，返回j-1
            if (q.isEmpty()) {
                return j - 1;
            }
        }
        // 遍历结束，返回最后一列的索引，即n-1
        return n - 1;
    }

}
